#ifndef LEETCODE_VEC_H
#define LEETCODE_VEC_H

#include <vector>
#include <iostream>

using namespace std;

/**************************************************************/
template<class T>
void print_vec(const vector<T>& nums, int n) {
    for(const T& elem : nums) {
        std::cout << elem << std::endl;
        if(--n == 0) return;
    }
}

template<class T>
void print_vec(const vector<T>& nums) {
    for(const T& elem : nums) {
        std::cout << elem << std::endl;
    }
}
/****************************************************************/


//! 704. 二分查找
int search(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1, medium;
    while(left <= right) {
        medium = (left + right) / 2;
        if(target < nums[medium]) {
            right = medium - 1;
        } else if(nums[medium] < target) {
            left = medium + 1;
        } else {
            return medium;
        }
    }
    return -1;
}

//! 35. 搜索插入位置
int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1, medium;
    while(left <= right) {
        medium = (left + right) / 2;
        if(target < nums[medium]) {
            right = medium - 1;
        } else if(nums[medium] < target) {
            left = medium + 1;
        } else {
            return medium;
        }
    }
    if (right < left) {
        return left;
    } else {
        return right;
    }
}

//! 34. 在排序数组中查找元素的第一个和最后一个位置
vector<int> searchRange(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    vector<int> res {-1, -1};
    while(left <= right) {
        int medium = (left + right) / 2;
        if(nums[medium] < target) {
            left = medium + 1;
        } else if(nums[medium] > target) {
            right = medium - 1;
        } else {
            res[0] = res[1] = medium;
            while(res[0] > 0 && nums[res[0] - 1] == target) {
                res[0]--;
            }
            while((res[1] < nums.size() - 1) && nums[res[1] + 1] == target) {
                res[1]++;
            }
            break;
        }
    }
    return res;
}

//! 69. x 的平方根
int mySqrt(int x) {
    if(x == 0) {
        return 0;
    }
    if(x < 4) {
        return 1;
    }
    if(x < 9) {
        return 2;
    }
    int left = 1, right = x / 3;
    while(left <= right) {
        unsigned long long medium = (left + right) / 2;
        if(medium * medium < x) {
            if((medium+1) * (medium+1) < x) {
                left = medium + 1;
            } else if((medium+1) * (medium+1) == x) {
                return medium + 1;
            } else {
                return medium;
            }
        } else if(medium * medium > x) {
            if((medium-1) * (medium-1) > x) {
                right = medium - 1;
            } else if((medium-1) * (medium-1) < x) {
                return medium - 1;
            } else {
                return medium;
            }
        } else {
            return medium;
        }
    }
}

//! 367. 有效的完全平方数
bool isPerfectSquare(int num) {
    int left = 0, right = num;
    while(left <= right) {
        unsigned long long medium = (left + right) / 2;
        if(medium * medium == num) {
            return true;
        } else if(medium * medium < num) {
            left = medium + 1;
        } else {
            right = medium - 1;
        }
    }
}

//! 27. 移除元素
int removeElement(vector<int>& nums, int val) {
    int n = nums.size();
    for(int i=0; i<n;) {
        if(nums[i] == val) {
            nums[i] = nums[n-1];
            n--;
            continue;
        }
        i++;
    }
    return n;
}

//! 26. 删除有序数组中的重复项
int removeDuplicates(vector<int>& nums) {
    int slow = 0;
    int fast = 0;
    while(1) {
        while(nums[fast] == nums[slow]) {
            fast++;
            if (fast == nums.size()) return slow + 1;
        }
        slow++;
        nums[slow] = nums[fast];
    }
}

//! 283. 移动零
void moveZeroes(vector<int>& nums) {
    int n = nums.size();

    int slow = 0;
    int fast = 0;
    while(1) {
        if(fast < n && nums[fast] == 0) {
            while (fast < n && nums[fast] == 0) {
                fast++;
            }
        }
        if(fast == n) break;
        nums[slow] = nums[fast];
        slow++;
        fast++;
    }

    for (int i = slow; i < n; i++) {
        nums[i] = 0;
    }
    return;

}

//! 977. 有序数组的平方
vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> res (n, 0);

    if(nums[0] >= 0) {
        for(int i=0 ; i < n; i++)  {
            res[i] = nums[i] * nums[i];
        }
        return res;
    }

    if(nums[n - 1] <= 0) {
        for(int i=0 ; i < n; i++)  {
            res[i] = nums[n-1-i] * nums[n-1-i];
        }
        return res;
    }

    int medium = 0;

    while (medium < n && nums[medium] < 0) {
        medium++;
    }
    int left = medium - 1;
    int right = medium;
    for(int i=0; i<n; i++) {
        if(nums[right] + nums[left] < 0) {
            res[i] = nums[right] * nums[right];
            right++;
        } else {
            res[i] = nums[left] * nums[left];
            left--;
        }
        if(right == n) {
            while(left >= 0) {
                res[++i] = nums[left] * nums[left];
                left--;
            }
            return res;
        }
        if(left < 0) {
            while(right < n) {
                res[++i] = nums[right] * nums[right];
                right++;
            }
            return res;
        }
    }
}

// !844. 比较含退格的字符串
bool backspaceCompare(string s, string t) {

    int s_id = s.size() - 1;
    int t_id = t.size() - 1;
    while (1) {
        while(t_id >= 0 && t[t_id] == '#') {
            int t_count = 1;
            while (t_count > 0) {
                t_id--;
                if(t_id >= 0 && t[t_id] == '#') {
                    t_count++;
                }
                t_id--;
                if(t_id >= 0 && t[t_id] == '#') {
                    t_count++;
                }
                t_count--;
            }
        }
        while(s_id >= 0 && s[s_id] == '#') {
            int s_count = 1;
            while (s_count > 0) {
                s_id--;
                if(s_id >= 0 && s[s_id] == '#') {
                    s_count++;
                }
                s_id--;
                if(s_id >= 0 && s[s_id] == '#') {
                    s_count++;
                }
                s_count--;
            }
        }
        if(s_id < 0 || t_id < 0) break;
        if(s[s_id] != t[t_id]) {
            return false;
        } else {
            t_id--;
            s_id--;
        }
    }
    if(s_id < 0 && t_id < 0) {
        return true;
    } else {
        return false;
    }
}

//! 209.长度最小的子数组
int minSubArrayLen(int target, std::vector<int>& nums) {
    int count = nums[0];
    size_t min_len = -1;
    size_t left = 0, right = 1;
    bool flag = false;
    while(!(right == nums.size() && count < target)) {
        while(right < nums.size() && count < target) {
            count += nums[right];
            right++;
        }
        if(count >= target) flag = true;
        while(count >= target ) {
            count -= nums[left];
            left++;
        }
        min_len = min(min_len, right - left + 1);
    }
    return flag ? min_len : 0;
}

//! 904.水果成篮
int totalFruit(std::vector<int>& fruits) {
    std::vector<int> category(2);
    category[0] = category[1] = fruits[0];
    for(int i=1;i<fruits.size();i++) {
        if(fruits[i] != fruits[0]) {
            category[1] = fruits[i];
            break;
        }
    }
    if(category[0] == category[1]) {
        return fruits.size();
    }
    size_t count = 0;
    size_t res = 0;
    std::vector<int> last_fruits(2, 0);
    int last_cat;
    for(int i=0; i<fruits.size();) {
        if(fruits[i] == category[0]) {
            last_cat = category[0];
            last_fruits[1] = 0;
            while(fruits[i] == category[0]) {
                last_fruits[0]++;
                count++;
                i++;
                if(i == fruits.size()) {
                    return std::max(res, count);
                }
            }
        } else if(fruits[i] == category[1]) {
            last_cat = category[1];
            last_fruits[0] = 0;
            while(fruits[i] == category[1]) {
                last_fruits[1]++;
                i++;
                count++;
                if(i == fruits.size()) {
                    return std::max(res, count);
                }
            }
        } else {
            res = std::max(res, count);
            if(last_cat == category[0]) {
                category[1] = fruits[i];
                count = last_fruits[0];
                last_fruits[1] = 0;
            } else {
                category[0] = fruits[i];
                count = last_fruits[1];
                last_fruits[0] = 0;
            }
        }
    }
    return res;
}

//! 76. 最小覆盖子串
string minWindow(string s, string t) {

}

//! 59. 螺旋矩阵 II
vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> res (n, vector<int> (n, 0));
    int cur_num = 1;
    int loop = 0;
    while(loop < n) {
        for(int i=loop; i<(n - loop - 1); i++) {
            res[loop][i] = cur_num;
            cur_num++;
        }
        for(int i=loop; i<(n - loop - 1); i++) {
            res[i][n - 1 - loop] = cur_num;
            cur_num++;
        }
        for(int i=n- 1 - loop; i>loop; i--) {
            res[n - 1 - loop][i] = cur_num;
            cur_num++;
        }
        for(int i=n -1 - loop; i>loop; i--) {
            res[i][loop] = cur_num;
            cur_num++;
        }
        loop++;
    }
    if(n % 2) {
        res[(n - 1) / 2][(n - 1) / 2] = n * n;
    }
    return res;
}

//! 54. 螺旋矩阵
vector<int> spiralOrder(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    int cur_num = 0;
    vector<int> res(m * n, 0);
    int loop = 0;
    while(loop < (min(m,n))) {
        for(int i=loop; i<(n - loop - 1); i++) {
            res[cur_num] = matrix[loop][i];
            cur_num++;
            if(cur_num == m * n) return res;
        }
        for(int i=loop; i<(m - loop - 1); i++) {
            res[cur_num] = matrix[i][n - 1 - loop];
            cur_num++;
            if(cur_num == m * n) return res;
        }
        for(int i=n- 1 - loop; i>loop; i--) {
            res[cur_num] = matrix[m - 1 - loop][i];
            cur_num++;
            if(cur_num == m * n) return res;
        }
        for(int i=m -1 - loop; i>loop; i--) {
            res[cur_num] = matrix[i][loop];
            cur_num++;
            if(cur_num == m * n) return res;
        }
        loop++;
    }
    if(m == n && m % 2) {
        res[m * n - 1] = matrix[(m - 1) / 2][(n - 1) / 2];
    }
    return res;
}

//! 1365. 有多少小于当前数字的数字
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n, 0);
    vector<int> cnt(101, 0);

    for(const auto& num : nums) {
        cnt[num]++;
    }

    for(int i=1; i<101; i++) {
        cnt[i] += cnt[i-1];
    }

    for(int i=0; i<n; i++) {
        res[i] = cnt[nums[i] - 1];
    }

    return res;
}
#endif
